package fireway;

/**
 * <p> 写一个能解决背包问题的程序，任意给定背包的容量以及一些列物品的重量，设把这些重量值存在一个数组中。 </p>
 * <p> 提示：递归方法knapsack()的参数是目标重量和剩下物品开始位置的数组下标。 </p>
 * <p> 2018年 07月 09日 星期一 </p>
 *
 * @author fireway
 */
public class Knapsack {
    // 可供选择的重量
    private int[] mArrayWeight;

    private boolean[] mArraySelect;

    public Knapsack(int[] array) {
        mArrayWeight = array;
        mArraySelect = new boolean[array.length];
    }

    public void knapsack(int total, int index) {
        if (total < 0 || (total > 0 && index >= mArrayWeight.length)) {
            // 没找到解决办法，直接返回
            return;
        } else {
            if (0 == total) {
                // 总重量为0，则找到解决办法了
                for (int i = 0; i < index; i++) {
                    if (mArraySelect[i]) {
                        System.out.print(mArrayWeight[i] + ", ");
                    }
                }
                System.out.println();
                return;
            }
            mArraySelect[index] = true;
            knapsack(total - mArrayWeight[index], index + 1);
            mArraySelect[index] = false;
            knapsack(total, index + 1);
        }
    }
}
